|
A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The rank of each page can be generated iteratively from the Google matrix using the power method. However, in order for the power method to converge, the matrix must be stochastic, irreducible and aperiodic. ==Adjacency matrix ''A'' and Markov matrix ''S''== In order to generate the Google matrix ''G'', we must first generate an adjacency matrix ''A'' which represents the relations between pages or nodes. Assuming there are ''N'' pages, we can fill out ''A'' by doing the following: # A matrix element is filled with 1 if node has a link to node , and 0 otherwise; this is the adjacency matrix of links. # A related matrix ''S'' corresponding to the transitions in a Markov chain of given network is constructed from ''A'' by dividing the elements of column "j" by a number of where is the total number of outgoing links from node ''j'' to all other nodes. The columns having zero matrix elements, corresponding to dangling nodes, are replaced by a constant value ''1/N''. Such a procedure adds a link from every sink, dangling state to every other node. # Now by the construction the sum of all elements in any column of matrix ''S'' is equal to unity. In this way the matrix ''S'' is mathematically well defined and it belongs to the class of Markov chains and the class of Perron-Frobenius operators. That makes ''S'' suitable for the PageRank algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Google matrix」の詳細全文を読む スポンサード リンク
|